二叉树的遍历

function Node (value) {
    this.value = value;
    this.left = null;
    this.right = null;
}

const a = new Node('a');
const b = new Node('b');
const c = new Node('c');
const d = new Node('d');
const e = new Node('e');
const f = new Node('f');
const g = new Node('g');

a.left = b;
a.right = c;
b.left = d;
b.right = e;
c.left = f;
c.right = g;

          a
    b            c
d       e     f      g

前序遍历（先根次序遍历）

• 先打印当前的，再打印左边的，再打印右边的。（ a - b - d - e - c - f - g ）

function f1 (root) {
    if (root == null) return;
    console.log(root.value);
    f1(root.left);
    f1(root.right);
}
f1(a);  //--> a b d e c f g

中序遍历（中跟次序遍历）

• 先打印左边的，再打印当前的，再打印右边的。（ d - b - e - a - f - c - g ）

function f2 (root) {
    if (root == null) return;
    f2(root.left);
    console.log(root.value);
    f2(root.right);
}
f2(a);  //--> d b e a f c g

后序遍历（后根次序遍历）

• 先打印左边的，再打印右边的，再打印当前的。（ d - e - b - f - g - c - a ）

function f3 (root) {
    if (root == null) return;
    f3(root.left);
    f3(root.right);
    console.log(root.value);
}
f3(a);  //--> d e b f g c a

根据 前序中序 还原二叉树

const qian = ['a', 'b', 'd', 'e', 'c', 'f', 'g'];
const zhong = ['d', 'b', 'e', 'a', 'f', 'c', 'g'];

function restore (front, middle) {
    if (front == null || middle == null || front.length == 0 || middle.length == 0 || front.length != middle.length) return null;
    const root = new Node(front[0]);
    const index = middle.indexOf(root.value);  // 找到根节点在中序遍历中的位置
    const frontLeft = front.slice(1, index + 1);
    const frontRight = front.slice(index + 1);
    const middleLeft = middle.slice(0, index);
    const middleRight = middle.slice(index + 1);
    root.left = restore(frontLeft, middleLeft);  // 还原左子树
    root.right = restore(frontRight, middleRight);  // 还原右子树
    return root;
}

function Node (value) {
    this.value = value;
    this.left = null;
    this.right = null;
}

restore(qian, zhong);  //--> 

根据 中序后序 还原二叉树

const zhong = ['d', 'b', 'e', 'a', 'f', 'c', 'g'];
const hou = ['d', 'e', 'b', 'f', 'g', 'c', 'a'];

function restore (middle, after) {
    if (middle == null || after == null || middle.length == 0 || after.length == 0 || middle.length != after.length) return null;
    const root = new Node(after[after.length - 1]);
    const index = middle.indexOf(root.value);
    const middleLeft = middle.slice(0, index);
    const middleRight = middle.slice(index + 1);
    const afterLeft = after.slice(0, index);
    const afterRight = after.slice(index, -1);
    root.left = restore(middleLeft, afterLeft);
    root.right = restore(middleRight, afterRight);
    return root;
}

function Node (value) {
    this.value = value;
    this.left = null;
    this.right = null;
}

restore(zhong, hou);  //-->